| description |
Nous nous intéressons dans cette thèse à des problèmes d'optimisation liés au domaine des réseaux. Ces problèmes sont d'une part des problèmes d'optimisation classiques'' dans lesquels nous cherchons à pallier la NP-difficulté d'un problème en proposant des algorithmes approchés, le plus souvent avec garantie de performance. D'autre part, nous avons considéré des problèmes dans lesquels les utisateurs du réseau sont indépendants et individualistes. Chaque utilisateur souhaite alors optimiser sa propre fonction objectif, qui peut être très différente de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser cette fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste. Les problémes que nous avons considérés sont des problémes d'ordonnancement et de routage.
|